A METHOD OF SYNTHESIS OF IRREDUNDANT CIRCUITS (IN ZHEGALKIN'S BASIS) ADMITTING SINGLE FAULT DIAGNOSTIC TEST SETS WITH CARDINALITY 1

Romanov Dmitriy Sergeevich, Candidate of physical and mathematical sciences, associate professor, sub-department of mathematical cybernetics, Lomonosov Moscow State University (1 Leninskie gory street, Moscow, Russia), romanov@cs.msu.ru

519.718

Background. Testing of combinational circuits is an important theoretical problem with applications to testing and verification of VLSI. The aim of this work is to demonstrate that for an arbitrary Boolean function it is possible to construct a circuit realizing this function and allowing a small single fault diagnosing test set (under inverse faults at outputs of gates).
Materials and methods. Circuit design methods based on Zhegalkin polinomials (canonical Reed-Muller polinomial forms) were used.
Results. It has been established that for an arbitrary Boolean function f, depending on n variables, there exists an irredundant combinational circuit (in the basis {x&y, x+y, 1}) realizing f and admitting the single fault diagnosing test set (under inverse faults at outputs of gates).

combinational circuit, fault diagnostic test set, inverse fault at output of gate, Shannon function, easily testable circuit.

1. Yablonskiy S. V., Chegis I. A. Uspekhi matematicheskikh nauk [Progress of mathematical sciences]. 1955, vol. 10, no. 4 (66), pp. 182–184.
2. Chegis I. A., Yablonskiy S. V. Trudy MIAN SSSR [Proceedings of MIAS USSR]. 1958, vol. 51, pp. 270–360.
3. Red'kin N. P. Nadezhnost' i diagnostika skhem [Reliability and diagnostics of circuits]. Moscow: Izd-vo MGU, 1992, 192 p.
4. Fujiwara H. Logic testing and design for testability. Cambridge, Massachusetts;London:MIT Press,1990,284p.
5. Reddy S. M. IEEE Trans. Comput. 1972, vol. 21, iss. 1, pp. 124–141.
6. Saluja K. K., Reddy S. M. IEEE Trans. Comput. 1975, vol. 24, no. 1, pp. 995–998.
7. Red'kin N. P. Vestnik Moskovskogo universiteta. Ser. 1. Matematika. Mekhanika [Bulletin of Moscow University. Series 1. Mathematics. Mechanics]. 1986, no. 1, pp. 72–74.
8. Red'kin N. P. Matematicheskie voprosy kibernetiki [Mathematical problems of cybernetics]. Issue 2. Moscow: Nauka, 1989, pp. 198–222.
9. Red'kin N. P. Izvestiya vuzov. Matematika [University proceedings. Mathematics]. 1988, no. 7, pp. 57–64.
10. Red'kin N. P. Vestnik Moskovskogo universiteta. Ser. 1. Matematika. Mekhanika [Bulletin of Moscow University. Series 1. Mathematics. Mechanics]. 1988, no. 2, pp. 17–21.
11. Red'kin N. P. Vestnik Moskovskogo universiteta. Ser. 1. Matematika. Mekhanika [Bulletin of Moscow University. Series 1. Mathematics. Mechanics]. 1992, no. 5, pp. 43–46.
12. Red'kin N. P. Vestnik Moskovskogo universieta. Ser. 1. Matematika. Mekhanika [Bulletin of Moscow University. Series 1. Mathematics. Mechanics]. 2007, no. 3, pp. 29–33.
13. Kovatsenko S. V. Vestnik Moskovskogo universiteta. Ser. 15. Vychislitel'naya matematika i kibernetika [Bulletin of Moscow University. Series 15. Calculus mathematics and cybernetics]. 2000, no. 2, pp. 45–47.
14. Kolyada S. S. Vestnik Moskovskogo universiteta. Ser. 1. Matematika. Mekhanika [Bulletin of Moscow University. Series 1. Mathematics. Mechanics]. 2011, no. 6, pp. 47–49.
15. Kolyada S. S. Diskretnyy analiz i issledovanie operatsiy [Discrete analysis and research of operations]. 2013, vol. 20, no. 2, pp. 58–74.
16. Kolyada S. S. Vestnik Moskovskogo universiteta. Ser. 1. Matema-tika. Mekhanika [Bulletin of Moscow University. Series 1. Mathematics. Mechanics]. 2013, no. 4, pp. 32–34.
17. Noskov V. N. Diskretnaya matematika [Discrete mathematics]. 1993, vol. 5, no. 4, pp. 3–23.
18. Hirayama T., Koda G., Nishitani Y., Shimizu K. IEICE Trans. Inf. & Syst. 1999, vol. E-82D, no. 9, pp. 1278–1286.
19. Hayes J. P. IEEE Trans. Comput. 1974, vol. C-23, no. 1, pp. 56–62.
20. Saluja K. K., Reddy S. M. IEEE Trans. Comput. 1974, vol. C-23, no. 1, pp. 552–554.
21. Inose H., Sakauchi M. Proc. First USA-Japan Computer Conf. 1972, pp. 426–430.
22. DasGupta S. IEEE Trans. Comput. 1980, vol. C-29, no. 11, pp. 1025–1029.
23. Goryashko A. P. Avtomatika i telemekhanika [Automation and remote control]. 1981, no. 1, pp. 145–153.
24. Red'kin N. P. Matematicheskie voprosy kibernetiki [Mathematical problems of cybernetics]. Issue 12. Moscow: Fizmatlit, 2003, pp. 217–230.
25. Borodina Yu. V. Vestnik Moskovskogo universiteta. Ser. 15. Vychislitel'naya matematika i kibernetika [Bulletin of Moscow University. Series 1. Calculus mathematics and cybernetics.]. 2008, no. 1, pp. 40–44.
26. Borodina Yu. V. Vestnik Moskovskogo universiteta. Ser. 1. Matematika. Mekhanika [Bulletin of Moscow University. Series 1. Mathematics. Mechanics]. 2008, no. 5, pp. 49–52.
27. Borodina Yu. V., Borodin P. A. Diskretnaya matematika [Discrete mathematics]. 2010, vol. 22, no. 3, pp. 127–133.
28. Borodina Yu. V. Problemy teoreticheskoy kibernetiki. Materialy XVII Mezhdunar. konf. (Kazan', 16–20 iyunya 2014 g.) [Problems of theoretical cybernetics. Proceedings of XVII International conference (Kazan, 16–20 June 2014)]. Kazan: Otechestvo, 2014, pp. 38–39.
29. Romanov D. S. Diskretnaya matematika [Discrete mathematics]. 2013, vol. 25, no. 2, pp. 104–120.
30. Romanov D. S. Vestnik Moskovskogo universiteta. Ser. 15. Vychislitel'naya matematika i kibernetika [Bulletin of Moscow University. Series 1. Calculus mathematics and cybernetics]. 2015, no. 1, pp. 30–37.
31. Romanov D. S. Diskretnaya matematika [Discrete mathematics]. 2014, vol. 26, no. 2, pp. 100–130.
32. Noskov V. N. Diskretnyy analiz [Discrete analysis]. 1975, no. 27, pp. 23–51.
33. Pogosyan G. R. O proveryayushchikh testakh dlya logicheskikh skhem [On fault detection testing of logic circuits]. Moscow: VTs AN SSSR, 1982, 57 p.